import java.util.HashMap;
import java.util.Map;

class Node {
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
    }

    public Node(int val, Node left, Node right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class DynamicProgram3 {
    Map<Node,Integer> f = new HashMap<>();//表示选择该节点
    Map<Node,Integer> g = new HashMap<>();//表示不选择该节点

    public int rob(Node root) {
        dfs(root);
        return Math.max(f.getOrDefault(root,0),g.getOrDefault(root,0));
    }

//    代码主要部分

    /**
     * 时间复杂度是 O(n)
     * 由于递归会使用到栈空间，空间代价是 O(n)
     * 哈希表的空间代价也是 O(n)，故空间复杂度也是 O(n)。
     * @param node
     */
    public void dfs(Node node) {
        if (node == null) {
            return;
        }
//        深度优先遍历   后序遍历
        dfs(node.left);
        dfs(node.right);


        f.put(node, node.val + g.getOrDefault(node.left,0)+g.getOrDefault(node.right,0));
//        该节点本身的val  +  该节点左右孩子节点未被选中的val            存入哈希表中


        g.put(node,Math.max(f.getOrDefault(node.left,0),g.getOrDefault(node.left,0))+
                Math.max(f.getOrDefault(node.right,0),g.getOrDefault(node.right,0)));
//        不选择该节点： 该节点的左孩子可能被选中也可能不被选中 求它们中的的最大值  +  该节点的右孩子也同理          存入哈希表中
    }






//    优化 省去哈希表的空间

    /**
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)   因为栈空间的使用代价依旧是O(n)
     * @param root
     * @return
     */
    public int rob2(Node root) {
        int[] result = dfs2(root);
//        0（因为是0）表示偷  1表示不偷
        return Math.max(result[0],result[1]);
    }
    public int[] dfs2(Node node) {
        if (node == null) {
            return new int[]{0,0};
        }
        int[] left = dfs2(node.left);
        int[] right = dfs2(node.right);

        int[] result = new int[]{0,0};
        result[0] = node.val + left[1] + right[1];
        result[1] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
        return result;
    }
}
